home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / include / linux / prio_tree.h < prev    next >
C/C++ Source or Header  |  2005-10-13  |  3KB  |  123 lines
  1. #ifndef _LINUX_PRIO_TREE_H
  2. #define _LINUX_PRIO_TREE_H
  3.  
  4. /*
  5.  * K&R 2nd ed. A8.3 somewhat obliquely hints that initial sequences of struct
  6.  * fields with identical types should end up at the same location. We'll use
  7.  * this until we can scrap struct raw_prio_tree_node.
  8.  *
  9.  * Note: all this could be done more elegantly by using unnamed union/struct
  10.  * fields. However, gcc 2.95.3 and apparently also gcc 3.0.4 don't support this
  11.  * language extension.
  12.  */
  13.  
  14. struct raw_prio_tree_node {
  15.     struct prio_tree_node    *left;
  16.     struct prio_tree_node    *right;
  17.     struct prio_tree_node    *parent;
  18. };
  19.  
  20. #include <linux/types.h>
  21.  
  22. struct prio_tree_node {
  23.     struct prio_tree_node    *left;
  24.     struct prio_tree_node    *right;
  25.     struct prio_tree_node    *parent;
  26.     unsigned long        start;
  27.     unsigned long        last;    /* last location _in_ interval */
  28. };
  29.  
  30. struct prio_tree_root {
  31.     struct prio_tree_node    *prio_tree_node;
  32.     unsigned short         index_bits;
  33.     unsigned short        raw;
  34.         /*
  35.          * 0: nodes are of type struct prio_tree_node
  36.          * 1: nodes are of type raw_prio_tree_node
  37.          */
  38. };
  39.  
  40. struct prio_tree_iter {
  41.     struct prio_tree_node    *cur;
  42.     unsigned long        mask;
  43.     unsigned long        value;
  44.     int            size_level;
  45.  
  46.     struct prio_tree_root    *root;
  47.     pgoff_t            r_index;
  48.     pgoff_t            h_index;
  49. };
  50.  
  51. static inline void prio_tree_iter_init(struct prio_tree_iter *iter,
  52.         struct prio_tree_root *root, pgoff_t r_index, pgoff_t h_index)
  53. {
  54.     iter->root = root;
  55.     iter->r_index = r_index;
  56.     iter->h_index = h_index;
  57.     iter->cur = NULL;
  58. }
  59.  
  60. #define __INIT_PRIO_TREE_ROOT(ptr, _raw)    \
  61. do {                    \
  62.     (ptr)->prio_tree_node = NULL;    \
  63.     (ptr)->index_bits = 1;        \
  64.     (ptr)->raw = (_raw);        \
  65. } while (0)
  66.  
  67. #define INIT_PRIO_TREE_ROOT(ptr)    __INIT_PRIO_TREE_ROOT(ptr, 0)
  68. #define INIT_RAW_PRIO_TREE_ROOT(ptr)    __INIT_PRIO_TREE_ROOT(ptr, 1)
  69.  
  70. #define INIT_PRIO_TREE_NODE(ptr)                \
  71. do {                                \
  72.     (ptr)->left = (ptr)->right = (ptr)->parent = (ptr);    \
  73. } while (0)
  74.  
  75. #define INIT_PRIO_TREE_ITER(ptr)    \
  76. do {                    \
  77.     (ptr)->cur = NULL;        \
  78.     (ptr)->mask = 0UL;        \
  79.     (ptr)->value = 0UL;        \
  80.     (ptr)->size_level = 0;        \
  81. } while (0)
  82.  
  83. #define prio_tree_entry(ptr, type, member) \
  84.        ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
  85.  
  86. static inline int prio_tree_empty(const struct prio_tree_root *root)
  87. {
  88.     return root->prio_tree_node == NULL;
  89. }
  90.  
  91. static inline int prio_tree_root(const struct prio_tree_node *node)
  92. {
  93.     return node->parent == node;
  94. }
  95.  
  96. static inline int prio_tree_left_empty(const struct prio_tree_node *node)
  97. {
  98.     return node->left == node;
  99. }
  100.  
  101. static inline int prio_tree_right_empty(const struct prio_tree_node *node)
  102. {
  103.     return node->right == node;
  104. }
  105.  
  106.  
  107. struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root,
  108.                 struct prio_tree_node *old, struct prio_tree_node *node);
  109. struct prio_tree_node *prio_tree_insert(struct prio_tree_root *root,
  110.                 struct prio_tree_node *node);
  111. void prio_tree_remove(struct prio_tree_root *root, struct prio_tree_node *node);
  112. struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter);
  113.  
  114. #define raw_prio_tree_replace(root, old, node) \
  115.     prio_tree_replace(root, (struct prio_tree_node *) (old), \
  116.         (struct prio_tree_node *) (node))
  117. #define raw_prio_tree_insert(root, node) \
  118.     prio_tree_insert(root, (struct prio_tree_node *) (node))
  119. #define raw_prio_tree_remove(root, node) \
  120.     prio_tree_remove(root, (struct prio_tree_node *) (node))
  121.  
  122. #endif /* _LINUX_PRIO_TREE_H */
  123.